﻿public class Solution {
    public int[][] Merge(int[][] intervals)
    {
        if (intervals is null || intervals.Length == 0) return intervals;
        
        List<int[]> result = new List<int[]>();
        
        // 排序
        Array.Sort(intervals, (int[] a, int[] b) =>
        {
            if (a[0].Equals(b[0])) return a[1].CompareTo(b[1]);
            return a[0].CompareTo(b[0]);
        });

        int start = intervals[0][0];
        int end = intervals[0][1];

        for (int i = 1; i < intervals.Length; i++)
        {
            if (end < intervals[i][0])
            {
                result.Add([start, end]);
                start = intervals[i][0];
            }
            end = Math.Max(end, intervals[i][1]);
        }
        result.Add([start, end]);
        return result.ToArray();
    }

    public static void Main(string[] args)
    {
        int[][] intervals = [[1, 3], [2, 6], [8, 10], [15, 18]];
        Solution solution = new Solution();
        int[][] result = solution.Merge(intervals);

        foreach (int[] res in result)
        {
            foreach (int r in res)
            {
                Console.Write($"{r} ");
            }
            Console.WriteLine();
        }
    }
}